import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here

        // 插入排序
        // if (array.length == 0) {
        //     return array;
        // }

        // int index = 0;
        // for (int i = 0; i < array.length; i++) {
        //     if (array[i] % 2 == 0) {
        //         continue;
        //     }
        //     else {
        //         int temp = array[i];
        //         int k = i;
        //         while (k > index) {
        //             array[k] = array[--k];
        //         }
        //         array[index++] = temp;
        //     }
        // }
        // return array;

        // 双指针
        int odd = 0;
        for (int num : array) {
            if (num % 2 == 1) {
                odd++;
            }
        }

        int x = 0;
        int y = odd;
        int[] res = new int[array.length];

        for (int num : array) {
            if (num % 2 == 0) {
                res[y++] = num;
            }
            else {
                res[x++] = num;
            }
        }

        return res;
    }
}